package com.zlk.algorithm.algorithm.sort.merge;


import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName MergerSort
 * @description: 归并排序  todo  非递归实现
 * @author: slfang
 * @create: 2024-01-04 18:16
 * @Version 1.0
 **/
public class MergerSort {

    @Test
    public void test (){
        int testTime = 500000;
        int maxSize = 30;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = SortUtils.getRandomArr(maxValue, maxSize);
            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            //sortNoRecursion(arr1);
            mergeSort(arr1);
            Arrays.sort(arr2);
            if (!SortUtils.isEqual(arr1, arr2)) {
                System.out.println("fail");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return ;
            }
        }
        System.out.println("success");
    }


    void mergeSort(int[] arr){
        if(arr.length<2||arr==null){
            return ;
        }
        //递归实现
        sort(arr,0,arr.length-1);

        //非递归
        //sortNoRecursion(arr);
    }


    void sort(int[] arr,int l,int r){
        if(l==r){
            return ;
        }
        int mid = l+((r-l)>>1);
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge2(arr,l,mid,r);
    }

    private void merge(int[] arr,int l,int mid,int r) {
        int lIndex = l;
        int rIndex = mid+1;
        int[] temp = new int[r-l+1];
        int index = 0;
        while (rIndex<=r&&lIndex<=mid){
//            if(arr[rIndex]>=arr[lIndex]){
//                //移动右边数组
//                temp[index++] = arr[lIndex++];
//            }else{
//                temp[index++] = arr[rIndex++];
//            }
            //优化
            temp[index++] =arr[rIndex]>=arr[lIndex]?arr[lIndex++]:arr[rIndex++];
        }
        while (rIndex<=r){
            temp[index++] = arr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] = arr[lIndex++];
        }
//        int j = 0;
//        for (int i = l; i <=r; i++) {
//            arr[i] = temp[j++];
//        }
        //优化
        for (int i = 0; i < temp.length; i++) {
            arr[l+i] = temp[i];
        }
    }





    private void merge2(int[] arr,int l,int mid,int r) {
        int lIndex = l;
        int rIndex = mid+1;
        int[] temp = new int[r-l+1];
        int index = 0;
        while (lIndex<=mid&&rIndex<=r){
            temp[index++] = arr[lIndex]<=arr[rIndex]?arr[lIndex++]:arr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] = arr[lIndex++];
        }
        while (rIndex<=r){
            temp[index++] = arr[rIndex++];
        }
        int j = l;
        for (int i = 0; i < temp.length; i++) {
            arr[j++] = temp[i];
        }
    }

}
